package LearnAlgorithm.f_字符串;

import java.util.Arrays;

public class r查找最长重复子串by高度数组 {
	public static void main(String[] args) {
		String string = "123232323";
		r查找最长重复子串by高度数组 demo = new r查找最长重复子串by高度数组();
		System.out.println("max repeat:" + demo.findMaxRepeatSubstring(string, demo));
	}
	
	/**
	 * 运用高度数组
	 * @param string
	 * @param demo
	 * @return
	 */
	public int findMaxRepeatSubstring(String string, r查找最长重复子串by高度数组 demo) {
		Suff[] suffArray = demo.makeSuffArray(string);
		int[] heightArray = demo.makeHeightArray(string, suffArray);
		int suffArrayIndex = 0;
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < heightArray.length; i++) {
			if (heightArray[i] > max) {
				max = heightArray[i];
				suffArrayIndex = i;
			}
		}
		
		for (int i = 0; i < suffArray.length; i++) {
			System.out.println(heightArray[i] + "\t" + string.substring(suffArray[i].getIndex(), string.length()));
		}
		
		System.out.println("max child:" + string.substring(suffArray[suffArrayIndex].getIndex(), suffArray[suffArrayIndex].getIndex() + max));
		
		return max;
	}
	
	public int[] makeHeightArray(String string, Suff[] suffArray) {
		int length = string.length();
		int[] rk = new int[length];
		int[] height = new int[length];
		int k = 0;
		for (int i = 0; i < length; i++) {
			rk[suffArray[i].getIndex()] = i;
		}
		for (int SfArrIndex = 0; SfArrIndex < length; SfArrIndex++) {
			int rkValue = rk[SfArrIndex];
			if (rkValue == 0) {
				height[0] = 0;
				continue;
			}
			int preSfArrIndex = suffArray[rkValue - 1].getIndex();
			if (k > 0) {
				k--;
			}
			while (preSfArrIndex + k < length && SfArrIndex + k < length) {
//				System.out.println(string.charAt(SfArrIndex + k));
//				System.out.println(string.charAt(SfArrIndex + k));
				if (string.charAt(SfArrIndex + k) != string.charAt(preSfArrIndex + k)) {
					break;
				}
				k++;
			}
			height[rkValue] = k;
		}
		return height;
	}
	
	public Suff[] makeSuffArray(String string) {
		int length = string.length();
		int[] rk = new int[length];
		Suff[] suffixArray = new Suff[length];
		for (int i = 0; i < length; i++) {
			suffixArray[i] = new Suff(string.charAt(i) + "", i);
		}
		Arrays.sort(suffixArray);
		rk[suffixArray[0].getIndex()] = 1;
		for (int i = 1; i < length; i++) {
			rk[suffixArray[i].getIndex()] = rk[suffixArray[i - 1].getIndex()];
			if (!suffixArray[i].getString().equals(suffixArray[i - 1].getString())) {
				rk[suffixArray[i].getIndex()]++;
			}
		}
		for (int k = 2; rk[suffixArray[length - 1].getIndex()] < length; k *= 2) {
			final int kk = k;
			Arrays.sort(suffixArray, (o1, o2) -> {
				int x = ((Suff) o1).getIndex();
				int y = ((Suff) o2).getIndex();
				if (rk[x] == rk[y]) {
					if (x + kk / 2 >= length || y + kk / 2 >= length) {
						return -(x - y);
					}
					return rk[x + kk / 2] - rk[y + kk / 2];
				} else {
					return rk[x] - rk[y];
				}
			});
			rk[suffixArray[0].getIndex()] = 1;
			for (int i = 1; i < length; i++) {
				int x = suffixArray[i].getIndex();
				int y = suffixArray[i - 1].getIndex();
				rk[x] = rk[y];
				try {
					if (!string.substring(x, x + kk).equals(string.substring(y, y + kk))) {
						rk[x]++;
					}
				} catch (Exception exception) {
					rk[x]++;
				}
			}
		}
		return suffixArray;
	}
	
	public class Suff implements Comparable<Suff> {
		private String string = null;
		private int index = 0;
		public Suff() {};
		public Suff(String string, int index) {
			this.string = string;
			this.index = index;
		}
		public void setString(String string) {
			this.string = string;
		}
		public String getString() {
			return string;
		}
		public void setIndex(int index) {
			this.index = index;
		}
		public int getIndex() {
			return index;
		}
		@Override
		public int compareTo(Suff other) {
			return this.string.compareTo(other.string);
		}
		@Override
		public String toString() {
            return "Suff {" +
                    "string='" + string + '\'' +
                    ", index=" + index +
                    '}';
        }
	}
}
